package 简单算法;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-22
 * @Description: 给定一个排序数组和一个目标值，如果在数组中找到目标值则返回索引。如果没有，返回到它将会被按顺序插入的位置。
 * 你可以假设在数组中无重复元素。
 * 样例
 * [1,3,5,6]，5 → 2
 * [1,3,5,6]，2 → 1
 * [1,3,5,6]， 7 → 4
 * [1,3,5,6]，0 → 0
 * 挑战
 * 时间复杂度为O(log(n))
 **/
public class 搜索插入位置 {
    public static void main(String[] args) {
        搜索插入位置 s = new 搜索插入位置();
        System.out.println(s.searchInsert(new int[]{1, 10, 201, 1001, 10001, 10007}, 10002));
    }

    public int searchInsert(int[] A, int target) {
        // write your code here
        if (A == null || A.length == 0) {
            return 0;
        }
        int start = 0;
        int end = A.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] == target) {
                end = mid;
            } else if (A[mid] < target) {
                //往右查找
                start = mid + 1;
            } else {
                //往左查找
                end = mid - 1;
            }
        }
        if (A[start] == target) {
            return start;
        } else if (target > A[start]) {
            return start + 1;
        } else {
            return start;
        }
    }
}
